{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Matchsticks to Square"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming #backtracking #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划 #回溯 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: makesquare"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #火柴拼正方形"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你将得到一个整数数组 <code>matchsticks</code> ，其中 <code>matchsticks[i]</code> 是第 <code>i</code>&nbsp;个火柴棒的长度。你要用 <strong>所有的火柴棍</strong>&nbsp;拼成一个正方形。你 <strong>不能折断</strong> 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 <strong>使用一次</strong> 。</p>\n",
    "\n",
    "<p>如果你能使这个正方形，则返回 <code>true</code> ，否则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/04/09/matchsticks1-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> matchsticks = [1,1,2,2,2]\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong> 能拼成一个边长为2的正方形，每边两根火柴。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> matchsticks = [3,3,3,3,4]\n",
    "<strong>输出:</strong> false\n",
    "<strong>解释:</strong> 不能用所有火柴拼成一个正方形。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= matchsticks.length &lt;= 15</code></li>\n",
    "\t<li><code>1 &lt;= matchsticks[i] &lt;= 10<sup>8</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [matchsticks-to-square](https://leetcode.cn/problems/matchsticks-to-square/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [matchsticks-to-square](https://leetcode.cn/problems/matchsticks-to-square/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,2,2,2]', '[3,3,3,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        n = len(matchsticks)\n",
    "        s = sum(matchsticks)\n",
    "        if s % 4:\n",
    "            return False\n",
    "        tgt = s // 4\n",
    "        matchsticks.sort(reverse=True)\n",
    "        used = [False] * len(matchsticks)\n",
    "        def dfs(idx, no, curr):\n",
    "            if no == 4:\n",
    "                return True\n",
    "            if curr == tgt:\n",
    "                return dfs(0, no+1, 0)\n",
    "                \n",
    "            for i in range(idx,n):\n",
    "                if i and not used[i - 1] and matchsticks[i] == matchsticks[i - 1]:\n",
    "                    continue\n",
    "                if used[i] or curr+matchsticks[i] > tgt:\n",
    "                    continue\n",
    "                used[i] = True\n",
    "                if dfs(i+1, no, curr+matchsticks[i]):\n",
    "                    return True\n",
    "                used[i] = False\n",
    "\n",
    "                if curr == 0:\n",
    "                    break\n",
    "\n",
    "        return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, nums: 'List[int]') -> 'bool':\n",
    "        if len(nums) < 4:\n",
    "            return False\n",
    "        _sum = sum(nums)\n",
    "        side, mod = divmod(_sum, 4)\n",
    "        if mod != 0 or max(nums) > side: return False\n",
    "        sides = [side] * 4\n",
    "        nums.sort(reverse=True)\n",
    "        return self._dfs(nums, 0, sides)\n",
    "\n",
    "\n",
    "    def _dfs(self, nums, n, sides):\n",
    "        if n == len(nums):return True\n",
    "        num = nums[n]\n",
    "        for i in range(4):\n",
    "            if sides[i] >= num:\n",
    "                sides[i] -= num\n",
    "                if self._dfs(nums, n+1, sides): return True\n",
    "                sides[i] += num\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        total,length = sum(nums),len(nums)\n",
    "        if total %4!=0 or length<4:\n",
    "            return False\n",
    "        nums.sort(reverse=True)\n",
    "        target = int(total/4)\n",
    "        used=[False]*length\n",
    "        def square(i,tar):\n",
    "            if i >=length:\n",
    "                return tar%target ==0\n",
    "            if used[i]:\n",
    "                return square(i+1,tar)\n",
    "            used[i]= True\n",
    "            if tar==nums[i]:\n",
    "                return True\n",
    "            if tar>nums[i]:\n",
    "                tar = tar-nums[i]\n",
    "                not_used = [j for j in range(i+1,length) if not used[j]]\n",
    "                for x in not_used:\n",
    "                    if square(x,tar):\n",
    "                        return True\n",
    "            used[i]=False\n",
    "            return False\n",
    "        for i in range(length):\n",
    "            if not square(i,target):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if sum(nums) % 4:\n",
    "            return False\n",
    "        else:\n",
    "            self.target = sum(nums) // 4\n",
    "        if not nums or len(nums) < 4:\n",
    "            return False\n",
    "        return self.backpack(nums,4)\n",
    "    \n",
    "    def backpack(self,nums,num_pack):\n",
    "        if num_pack == 1:\n",
    "            return True if sum(nums) == self.target else False\n",
    "        numsLen = len(nums)\n",
    "        if sum(nums) != self.target * num_pack:\n",
    "            return False\n",
    "        \n",
    "        already = []    #our first backpack\n",
    "        length = 0  #the number of items in our first backpack\n",
    "        nextPos = 0 #the position of the next item to be added\n",
    "        weight = 0\n",
    "        \n",
    "        nums.sort()\n",
    "        while weight < self.target:\n",
    "            if nextPos < numsLen:   #valid pos\n",
    "                already.append((nextPos,nums[nextPos]))\n",
    "                weight += nums[nextPos]\n",
    "                length += 1\n",
    "                nextPos += 1\n",
    "            else:\n",
    "                found = False\n",
    "                for pos in range(length - 1):\n",
    "                    if already[pos][0] - already[pos + 1][0] < -1:\n",
    "                        found = True\n",
    "                        lastOne = pos\n",
    "                if not found:\n",
    "                    return False\n",
    "                else:\n",
    "                    nextPos = already[lastOne][0] + 1\n",
    "                    already = already[:lastOne]\n",
    "                    weight = sum([element[0] for element in already])\n",
    "                    length = len(already)\n",
    "            \n",
    "            if weight == self.target:\n",
    "                chosen = {element[0] for element in already}\n",
    "                leftover = [nums[i] for i in range(numsLen) if i not in chosen]\n",
    "                if self.backpack(leftover,num_pack - 1):\n",
    "                    return True\n",
    "                else:\n",
    "                    lastIndex,lastWeight = already.pop()\n",
    "                    weight -= lastWeight\n",
    "                    length -= 1\n",
    "                    nextPos = lastIndex + 1\n",
    "                    if length == 0:\n",
    "                        return False\n",
    "                    else:\n",
    "                        lastIndex,lastWeight = already.pop()\n",
    "                        weight -= lastWeight\n",
    "                        length -= 1\n",
    "                        nextPos = lastIndex + 1\n",
    "            elif weight > self.target:\n",
    "                lastIndex,lastWeight = already.pop()\n",
    "                weight -= lastWeight\n",
    "                length -= 1\n",
    "                nextPos = lastIndex + 1\n",
    "                if length == 0:\n",
    "                    return False\n",
    "                else:\n",
    "                    lastIndex,lastWeight = already.pop()\n",
    "                    weight -= lastWeight\n",
    "                    length -= 1\n",
    "                    nextPos = lastIndex + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, nums: List[int]) -> bool:\n",
    "        nums.sort(reverse = True)\n",
    "        if sum(nums) % 4 != 0 or len(nums) < 4:\n",
    "            return False\n",
    "        else:\n",
    "            length = sum(nums) // 4\n",
    "        if nums[0] > length:\n",
    "            return False\n",
    "        used = set()\n",
    "        def back(k,value,start):\n",
    "            if k == 0:\n",
    "                return True\n",
    "            if value == length:\n",
    "                return back(k-1,0,0)\n",
    "            \n",
    "            for i in range(start,len(nums)):\n",
    "                if nums[i] + value <= length and i not in used:\n",
    "                    used.add(i)\n",
    "                    if back(k,value + nums[i],i+1):\n",
    "                        return True\n",
    "                    else:\n",
    "                        used.remove(i)\n",
    "            return False\n",
    "        return back(4,0,0)\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, nums: List[int]) -> bool:\n",
    "        memo = [0, 0, 0, 0]\n",
    "        nums.sort(reverse = True)\n",
    "        quarter = sum(nums) // 4\n",
    "        if quarter * 4 != sum(nums) or not nums: return False\n",
    "        def dfs(i):\n",
    "            if i >= len(nums):\n",
    "                return memo.count(quarter) == 4\n",
    "            for index, l in enumerate(memo):\n",
    "                if l not in memo[:index] and l + nums[i] <= quarter:\n",
    "                    memo[index] += nums[i]\n",
    "                    #print(memo)\n",
    "                    if dfs(i+1):\n",
    "                        return True\n",
    "                    else:\n",
    "                        memo[index] -= nums[i]\n",
    "            return False\n",
    "        return dfs(0)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, nums: List[int]) -> bool:\n",
    "        if not nums:\n",
    "            return False\n",
    "        L = len(nums)\n",
    "        perimeter = sum(nums)\n",
    "        possible_side =  perimeter // 4\n",
    "        if possible_side * 4 != perimeter:\n",
    "            return False\n",
    "        nums.sort(reverse=True)\n",
    "        sums = [0 for _ in range(4)]\n",
    "        def dfs(index):\n",
    "            if index == L:\n",
    "                return sums[0] == sums[1] == sums[2] == possible_side\n",
    "            for i in range(4):\n",
    "                if sums[i] + nums[index] <= possible_side:\n",
    "                    sums[i] += nums[index]\n",
    "                    if dfs(index + 1):\n",
    "                        return True\n",
    "                    sums[i] -= nums[index]\n",
    "            return False        \n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, nums: List[int]) -> bool:\n",
    "\n",
    "        def check(state, length):\n",
    "            if length == 0:\n",
    "                return state, True\n",
    "            if length <0:\n",
    "                return state, False\n",
    "            for i in range(len(nums)):\n",
    "                if state[i]: continue\n",
    "                state[i]= 1\n",
    "                state, flag = check(state, length-nums[i])\n",
    "                if flag:\n",
    "                    return state, True\n",
    "                state[i] = 0\n",
    "            return state, False\n",
    "\n",
    "        if len(nums)<4: return False\n",
    "        if sum(nums)%4 != 0: return False\n",
    "        length = sum(nums)/4\n",
    "        nums.sort(reverse=True)\n",
    "        state = [0]*len(nums)\n",
    "        for i in range(4):\n",
    "\n",
    "            j = 0\n",
    "            while state[j]:\n",
    "                j += 1\n",
    "            if nums[j]>length: return False\n",
    "\n",
    "            state[j] = 1\n",
    "            state, flag = check(state,length-nums[j])\n",
    "            print(i, state, flag)\n",
    "            if not flag: return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, nums: List[int]) -> bool:\n",
    "        if not nums:\n",
    "            return False\n",
    "        x = sum(nums)\n",
    "        if x % 4 != 0:\n",
    "            return False\n",
    "        \n",
    "        x = x//4\n",
    "        res = [0,0,0,0]\n",
    "        nums.sort(reverse = True)\n",
    "        if nums[0] > x:\n",
    "            return False\n",
    "        n = len(nums)\n",
    "        if n < 4:\n",
    "            return False\n",
    "\n",
    "        def search(i):\n",
    "            if i == n:\n",
    "                if res[0] == res[1] == res[2] == res[3] == x:\n",
    "                    return True\n",
    "                return False\n",
    "            \n",
    "            for j in range(4):\n",
    "                if res[j] + nums[i] <= x:\n",
    "                    res[j] += nums[i]\n",
    "                    if search(i+1):\n",
    "                        return True\n",
    "                    res[j] -= nums[i]\n",
    "\n",
    "            return False\n",
    "\n",
    "        return search(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, nums: List[int]) -> bool:\n",
    "        total = sum(nums)\n",
    "        if total % 4 != 0:\n",
    "            return False\n",
    "        target = total//4\n",
    "        nums.sort()\n",
    "        return self.dfs(nums, target, 0, 0, {})\n",
    "        \n",
    "    def dfs(self, nums, target, tmp, res, memo):\n",
    "        if not nums:\n",
    "            if res == 4:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        if (tuple(nums), tmp, res) in memo:\n",
    "            return memo[(tuple(nums), tmp, res)]\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if tmp + nums[i] == target:\n",
    "                if self.dfs(nums[:i] + nums[i+1:], target, 0, res + 1, memo):\n",
    "                    memo[(tuple(nums), tmp, res)] = True\n",
    "                    return True\n",
    "            elif tmp + nums[i] < target:\n",
    "                if self.dfs(nums[:i]+nums[i+1:], target, tmp + nums[i], res, memo):\n",
    "                    memo[(tuple(nums), tmp, res)] = True\n",
    "                    return True\n",
    "            else:\n",
    "                break\n",
    "        memo[(tuple(nums), tmp, res)] = False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, nums: List[int]) -> bool:\n",
    "        def dfs(nums, target, pos):  # pos为指向nums的指针\n",
    "            if pos == len(nums): return True  \n",
    "            for i in range(4):  # 对4个边的目标值进行遍历\n",
    "                if nums[pos] <= target[i]:  # nums中的某个值 <= 某目标值,才符合题意\n",
    "                    target[i] -= nums[pos]  # 更改目标值为最新的情况\n",
    "                    if dfs(nums, target, pos + 1): return True  # 找到了一个目标值的边\n",
    "                    target[i] += nums[pos]  # 如果没找到目标值的边, 则应该清除掉 对目标值的更改\n",
    "                else:  # 说明找到了一个目标值的边\n",
    "                    continue\n",
    "            return False\n",
    "\n",
    "         # 火柴数量少于4，或火柴长度总和不是4的整数倍时，返回False\n",
    "        if len(nums) < 4 or sum(nums) % 4 != 0: return False \n",
    "        nums.sort(reverse=True)  # 进行降序,提升速度\n",
    "        target = [sum(nums) // 4] * 4  # 四个边的目标值\n",
    "        return dfs(nums, target, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        n = len(matchsticks)\n",
    "        total = sum(matchsticks)\n",
    "        if (total % 4 != 0): return False\n",
    "        target = total // 4\n",
    "        for match in matchsticks:\n",
    "            if match > target: return False\n",
    "        matchsticks.sort(reverse=True)\n",
    "        edges = [0] * 4\n",
    "\n",
    "        def dfs(idx: int) -> bool:\n",
    "            if idx == n:\n",
    "                return True\n",
    "            for i in range(4):\n",
    "                if edges[i] + matchsticks[idx] > target:\n",
    "                    continue\n",
    "                edges[i] += matchsticks[idx]\n",
    "                if (dfs(idx + 1)):\n",
    "                    return True\n",
    "                edges[i] -= matchsticks[idx]\n",
    "            return False\n",
    "        \n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        targetLen = sum(matchsticks) / 4\n",
    "        if int(targetLen)**2 != targetLen**2:\n",
    "            return False\n",
    "\n",
    "        sides = [0] * 4      # L T R B\n",
    "        matchsticks.sort(reverse=True)\n",
    "        \n",
    "        def dfs(i):\n",
    "            if i == len(matchsticks):\n",
    "                return True\n",
    "            \n",
    "            for j in range(4):\n",
    "                if sides[j] + matchsticks[i] <= targetLen:\n",
    "                    sides[j] += matchsticks[i]\n",
    "                    if dfs(i + 1):\n",
    "                        return True\n",
    "                    sides[j] -= matchsticks[i]\n",
    "            return False\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        totalLen = sum(matchsticks)\n",
    "        if totalLen % 4:\n",
    "            return False\n",
    "        tLen = totalLen // 4\n",
    "\n",
    "        dp = [-1] * (1 << len(matchsticks))\n",
    "        dp[0] = 0\n",
    "        for s in range(1, len(dp)):\n",
    "            for k, v in enumerate(matchsticks):\n",
    "                if s & (1 << k) == 0:\n",
    "                    continue\n",
    "                s1 = s & ~(1 << k)\n",
    "                if dp[s1] >= 0 and dp[s1] + v <= tLen:\n",
    "                    dp[s] = (dp[s1] + v) % tLen\n",
    "                    break\n",
    "        return dp[-1] == 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        def add_stick(i, sticks):\n",
    "            nonlocal side_length\n",
    "            if i == len(matchsticks):\n",
    "                return len(set(sticks)) == 1\n",
    "            for j in range(4):\n",
    "                sticks[j] += matchsticks[i]\n",
    "                if sticks[j] <= side_length and add_stick(i+1, sticks):\n",
    "                    return True\n",
    "                sticks[j] -= matchsticks[i]\n",
    "            return False \n",
    "\n",
    "        if (side_length := sum(matchsticks)) % 4:\n",
    "            return False \n",
    "        side_length //= 4\n",
    "        matchsticks.sort(reverse=True)\n",
    "        return add_stick(0, [0] * 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        def get_all_groups(matchsticks,n,v):\n",
    "            if v==0:\n",
    "                return {()}\n",
    "            if n==1:\n",
    "                if v in matchsticks:\n",
    "                    return {(v,)}\n",
    "                return {}\n",
    "            result=set()\n",
    "            for i in range(len(matchsticks)):\n",
    "                rs=get_all_groups(matchsticks[i+1:],n-1,v-matchsticks[i])\n",
    "                for r in rs:\n",
    "                    result.add((matchsticks[i],)+r)\n",
    "            return result\n",
    "            \n",
    "        def recur(matchsticks,b,num):\n",
    "            #print(matchsticks,b,num)\n",
    "            if num==0:\n",
    "                return True\n",
    "            if matchsticks[0]==b:\n",
    "                return recur(matchsticks[1:],b,num-1)\n",
    "            if b-matchsticks[0] in matchsticks[1:]:\n",
    "                i=matchsticks.index(b-matchsticks[0])\n",
    "                if i==0:\n",
    "                    i=1\n",
    "                return recur(matchsticks[1:i]+matchsticks[i+1:],b,num-1)\n",
    "            if num==1:\n",
    "                return True\n",
    "            min_n=len(matchsticks)//num\n",
    "            all_groups=get_all_groups(matchsticks,min_n,b)\n",
    "            #print('GGGG',all_groups)\n",
    "            for g in all_groups:\n",
    "                ms=matchsticks[:]\n",
    "                for i in g:\n",
    "                    ms.remove(i)\n",
    "                if recur(ms,b,num-1):\n",
    "                    return True\n",
    "            return False\n",
    "                \n",
    "\n",
    "            \n",
    "\n",
    "        b=sum(matchsticks)\n",
    "        if b%4!=0:\n",
    "            return False\n",
    "        b=b//4\n",
    "\n",
    "        matchsticks.sort()\n",
    "        if matchsticks[0]>b:\n",
    "            return False\n",
    "        \n",
    "        return recur(matchsticks,b,4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        total = sum(matchsticks)\n",
    "        if total % 4: return False\n",
    "        t = total // 4\n",
    "        n = len(matchsticks)\n",
    "\n",
    "        dp = [-1] * (1 << n)\n",
    "        dp[0] = 0\n",
    "        for s in range(1, 1 << n):\n",
    "            for k, v in enumerate(matchsticks):\n",
    "                if s & (1 << k) == 0: continue\n",
    "                s1 = s & ~(1 << k)\n",
    "                if dp[s1] >= 0 and dp[s1] + v <= t:\n",
    "                    dp[s] = (dp[s1] + v) % t \n",
    "                    # print(\"s, k, v, dp\", s, k, v, dp)\n",
    "                    break\n",
    "                \n",
    "        return dp[-1] == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        k = 4 \n",
    "        tot = sum(matchsticks)\n",
    "        if tot % 4 != 0:\n",
    "            return False \n",
    "        n = len(matchsticks)\n",
    "        dp = [0] * (1 << n)\n",
    "        cursum = [0] * (1 << n)\n",
    "        dp[0] = 1\n",
    "        per = tot // 4\n",
    "        print(per, tot )\n",
    "        for i in range(1 << n):\n",
    "            if dp[i]:\n",
    "                for j in range(n):\n",
    "                    if ((i >> j)& 1) == 0 and cursum[i] + matchsticks[j] <=per:\n",
    "                        nxt = i | (1 << j)\n",
    "                        cursum[nxt] = (cursum[i] + matchsticks[j]) % per \n",
    "                        dp[nxt] = 1\n",
    "        return dp[(1 <<n) -1]==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, stat, cur_sum, count):\n",
    "        if stat in self.s_dic:\n",
    "            return self.s_dic[stat]\n",
    "\n",
    "        ans = False\n",
    "        for i, stick in enumerate(self.matchsticks):\n",
    "            if stat >> i & 1 == 0:\n",
    "                if cur_sum + stick < self.tar:\n",
    "                    ans |= self.dfs(stat | 1 << i, cur_sum + stick, count)\n",
    "                elif cur_sum + stick == self.tar:\n",
    "                    if count == 3:\n",
    "                        self.s_dic[stat] = True\n",
    "                        return True\n",
    "                    ans |= self.dfs(stat | 1 << i, 0, count + 1)\n",
    "                if ans:\n",
    "                    self.s_dic[stat] = ans\n",
    "                    return ans\n",
    "        self.s_dic[stat] = ans\n",
    "        return ans\n",
    "\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        self.s_dic = {}\n",
    "        self.matchsticks = matchsticks\n",
    "        s = sum(matchsticks)\n",
    "        if s % 4 != 0:\n",
    "            return False\n",
    "        self.tar = int(s / 4)\n",
    "        return self.dfs(0, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        matchsticks = sorted(matchsticks)\n",
    "        sum_all = sum(matchsticks)\n",
    "        if not (sum_all % 4 == 0):\n",
    "            return False\n",
    "        dp = {}\n",
    "        \n",
    "        def search(tar, count, visited):\n",
    "            if tar < 0:\n",
    "                return False\n",
    "            if tar == 0:\n",
    "                count += 1\n",
    "                tar = sum_all // 4\n",
    "                if count == 4:\n",
    "                    return True\n",
    "            if not dp.get(visited, None) == None:\n",
    "                return dp.get(visited, None)\n",
    "            res = False\n",
    "            pre = 0\n",
    "            for i in range(len(matchsticks)):\n",
    "                if (visited >> i) & 1:\n",
    "                    continue\n",
    "                if matchsticks[i] == pre:\n",
    "                    continue\n",
    "                pre = matchsticks[i]\n",
    "                res = res or search(tar - matchsticks[i], count, visited | (1 << i))\n",
    "                if res:\n",
    "                    break\n",
    "            dp[visited] = res\n",
    "            return res\n",
    "        \n",
    "        return search(sum_all//4, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        s = sum(matchsticks)\n",
    "        if s%4 != 0: return False\n",
    "        target = s//4\n",
    "        matchsticks.sort(reverse=True)\n",
    "        n = len(matchsticks)\n",
    "        full = (1<<n) -1\n",
    "\n",
    "        @cache\n",
    "        def dp(mask,score):\n",
    "            if mask == full: return True\n",
    "            pre = -1\n",
    "            for i in range(n):\n",
    "                if matchsticks[i] + score > target: continue\n",
    "                if mask>>i & 1: continue\n",
    "                if matchsticks[i] == pre: continue\n",
    "                pre = matchsticks[i]\n",
    "                if dp(mask|1<<i,(score+matchsticks[i])%target): return True\n",
    "            return False\n",
    "        \n",
    "        return dp(0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "if not __file__.endswith(\"prog_joined.py\"):\n",
    "    from typing import *\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        S = sum(matchsticks)\n",
    "        N = len(matchsticks)\n",
    "        if S % 4 != 0:\n",
    "            return False\n",
    "        bian = S//4\n",
    "        sums = [0]*(1 << N)\n",
    "        for i, m in enumerate(matchsticks):\n",
    "            if m > bian:\n",
    "                return False\n",
    "            sums[1 << i] = m\n",
    "        candis = []\n",
    "        for mask in range(1 << N):\n",
    "            lsb = (1 + (mask ^ (mask-1))) >> 1\n",
    "            sums[mask] = sums[mask ^ lsb]+sums[lsb]\n",
    "            if sums[mask] == bian:\n",
    "                candis.append(mask)\n",
    "                # if not __file__.endswith(\"prog_joined.py\"):\n",
    "                #     pprint(f'{mask:016b}')\n",
    "\n",
    "        def backtrack(i, mask):\n",
    "            if mask+1 == 1 << N:\n",
    "                return True\n",
    "            if i == len(candis):\n",
    "                return False\n",
    "            return (mask & candis[i] == 0 and backtrack(i+1, mask | candis[i])) or backtrack(i+1, mask)\n",
    "\n",
    "        return backtrack(0, 0)\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\" and not __file__.endswith(\"prog_joined.py\"):\n",
    "    from leetcode_loming import auto_run, get_class, get_last_arg\n",
    "    from itertools import *\n",
    "    from pprint import pprint\n",
    "    import args\n",
    "    from rich.progress import track\n",
    "    Class = get_class()\n",
    "    arg = get_last_arg(args)\n",
    "    arg = args.args_lc\n",
    "    arg = args.arg0\n",
    "    pprint(arg)\n",
    "    res, time_cost = auto_run(Class, arg)\n",
    "    pprint(res)\n",
    "    pprint(time_cost)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        s = sum(matchsticks)\n",
    "        if s%4 != 0: return False\n",
    "        target = s//4\n",
    "        matchsticks.sort()\n",
    "        n = len(matchsticks)\n",
    "        full = (1<<n) -1\n",
    "\n",
    "        @cache\n",
    "        def dp(mask,score):\n",
    "            if mask == full: return True\n",
    "            pre = -1\n",
    "            for i in range(n):\n",
    "                if matchsticks[i] + score > target: continue\n",
    "                if mask>>i & 1: continue\n",
    "                if matchsticks[i] == pre: continue # 同一个位置不再重复尝试相同的值\n",
    "                pre = matchsticks[i]\n",
    "                if dp(mask|1<<i,(score+matchsticks[i])%target): return True # 学到的取余\n",
    "            return False\n",
    "        \n",
    "        return dp(0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "    #     totalLen = sum(matchsticks)\n",
    "\n",
    "    #     if totalLen % 4 != 0:\n",
    "    #         return False\n",
    "    #     matchsticks.sort(reverse=True)\n",
    "    #     edges = [0] * 4\n",
    "        \n",
    "    #     def backward(idx):\n",
    "    #         if idx == len(matchsticks):\n",
    "    #             return True\n",
    "    #         for i in range(4):\n",
    "    #             edges[i] += matchsticks[idx]\n",
    "    #             if edges[i] <= totalLen // 4 and backward(idx + 1):\n",
    "    #                 return True\n",
    "    #             edges[i] -= matchsticks[idx]\n",
    "    #         return False\n",
    "        \n",
    "    #     return backward(0)\n",
    "\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        edge, remain = divmod(sum(matchsticks), 4)\n",
    "        if remain: return False\n",
    "        matchsticks.sort(reverse=True)\n",
    "        @cache\n",
    "        def backtrace(u, st, cnt, status):\n",
    "            if u == edge:\n",
    "                if cnt + 1 == 4: return True\n",
    "                u = st = 0\n",
    "                cnt += 1\n",
    "            for i, x in enumerate(matchsticks[st:], st):\n",
    "                if ((status >> i) & 1) == 1: continue\n",
    "                if u + x > edge: continue\n",
    "                status |= 1 << i\n",
    "                if backtrace(u + x, i + 1, cnt, status): return True\n",
    "                status ^= 1 << i\n",
    "                if u == 0 or u + x == edge: break\n",
    "            return False\n",
    "        \n",
    "        return backtrace(0, 0, 0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 显然要把所有火柴棍装进4个sum/4的桶里。\n",
    "    # 可以继续使用记忆化搜索。记忆化搜索是比DP还爽的东西，我都不想想DP了以后。\n",
    "\n",
    "    # 状态：一个int储存最多15位咯；以及一个存储边长桶余数的状态\n",
    "    # 奇妙的dp/dfs条件：不需要储存4个桶的状态，只需要储存每个桶的状态的余数。因为储存4个桶需要关注现在存到哪个桶了，平添一堆的计算量；而只存一条边会简单很多，反正只有【当火柴全部放完】时候的状态才会到达4个全满。所以不需要考虑多个桶。\n",
    "    # 硬要用多个桶也不是不行，其实加一个用于记录桶数的变量bucket_num即可。只不过到最后会发现bucket_num用不上而已。    反之，如果不是正方形而是什么别的形状，那么bucket_num很可能就能用上，那就是另一番景象了。\n",
    "    # 注意：【state】虽然只是一个int，但是包含了目前的完整状态。因为，一个特顶的火柴棍集合，就是对应一个长度。没有第二种对应。\n",
    "\n",
    "    # dfs方式：从全0状态开始，不断尝试add一个火柴棍。遇到死路则放置-1。dp[state]存放其余数（其实也可以不存放余数，只存放True和False，因为余数可以现场算。但是存放了更省空间）。\n",
    "    # 这个题的想法实际上有些难的，没有那么直接和简单。其实算是比较难的dp题，我觉得算是hard\n",
    "    # And here we go!\n",
    "\n",
    "    # 最后一个核心点：一个状态，是否一定对应了【成与不成】？会不会同一个火柴集合，另外一个放法就成了？\n",
    "    # 答：不可能。首先，在第一个桶内不可能出现这个问题；其次，在第二个桶内，那个时候的state必然包含某一个 第一个桶 的合格解。如果第一个桶不合格，就到不了第二个桶，所以如果第二个桶不成了，那也是第二个桶的问题。这样的分析使得第二个桶内也一定不会出现“成与不成”的问题。\n",
    "    # 这是这道题最难的部分，很难想的特别清楚。\n",
    "\n",
    "    # 一遍过，真爽。\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        self.n = len(matchsticks)\n",
    "        self.matchsticks = matchsticks\n",
    "        total = sum(matchsticks)\n",
    "        if total % 4 != 0:\n",
    "            return False\n",
    "        self.edge = total // 4\n",
    "        self.dp = {} # 当没有火柴时，余数为0.\n",
    "        self.full = 0\n",
    "        for i in range(self.n):\n",
    "            self.full = self.full | (1<<i)\n",
    "        return self.dfs(0, 0)\n",
    "        \n",
    "\n",
    "    def dfs(self, state, remainder): # remainder是余数之前的一个数，处理即可\n",
    "        if state in self.dp:\n",
    "            return self.dp[state]\n",
    "        \n",
    "        if remainder >= self.edge:\n",
    "            if remainder > self.edge:\n",
    "                self.dp[state] = False\n",
    "                return False\n",
    "            else:\n",
    "                remainder = 0\n",
    "        if state == self.full:\n",
    "            if remainder == 0:\n",
    "                self.dp[state] = True\n",
    "                return True\n",
    "            else:\n",
    "                self.dp[state] = False\n",
    "                return False\n",
    "            \n",
    "        for i in range(self.n): # 对每一个不在集合中的火柴棍进行增加。\n",
    "            if (state>>i) & 1 == 0:\n",
    "                if self.dfs(state | (1<<i), remainder + self.matchsticks[i]):\n",
    "                    self.dp[state] = True\n",
    "                    return True\n",
    "        self.dp[state] = False\n",
    "        return False\n",
    "                \n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        Runtime: 279 ms, faster than 81.04% \n",
    "        Memory Usage: 18.6 MB, less than 24.17% \n",
    "\n",
    "        1 <= matchsticks.length <= 15\n",
    "        1 <= matchsticks[i] <= 10^8\n",
    "        \"\"\"\n",
    "        l, m = divmod(sum(matchsticks), 4)\n",
    "        if m > 0 or any(x > l for x in matchsticks):\n",
    "            return False\n",
    "\n",
    "        matchsticks.sort(reverse=True)\n",
    "        stack = [(1, matchsticks[0], 0, 0, 0)]\n",
    "        seen = set()\n",
    "\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            pos, borders = node[0], node[1:]\n",
    "            if all(x == l for x in borders):\n",
    "                return True\n",
    "            if pos >= len(matchsticks) or any(x > l for x in borders):\n",
    "                continue\n",
    "            if tuple(sorted(borders)) in seen:\n",
    "                continue\n",
    "            seen.add(tuple(sorted(borders)))\n",
    "            value = matchsticks[pos]\n",
    "            stack.append((pos + 1, borders[0] + value, borders[1], borders[2], borders[3]))\n",
    "            stack.append((pos + 1, borders[0], borders[1] + value, borders[2], borders[3]))\n",
    "            stack.append((pos + 1, borders[0], borders[1], borders[2] + value, borders[3]))\n",
    "            stack.append((pos + 1, borders[0], borders[1], borders[2], borders[3] + value))\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef makesquare(self, matchsticks):\n",
    "\t\tn, s = len(matchsticks), sum(matchsticks)\n",
    "\t\tif n == 0 or s % 4 != 0: return False\n",
    "\t\t@lru_cache(None)\n",
    "\t\tdef calc(m): return sum(matchsticks[i] for i in range(n) if (m & (1 << i)))\n",
    "\t\tfor x in range(1, 1 << n):\n",
    "\t\t\tif calc(x) != s // 2: continue\n",
    "\t\t\tm, ok = x, False\n",
    "\t\t\twhile m != 0:\n",
    "\t\t\t\tif calc(m) == s // 4: ok = True; break\n",
    "\t\t\t\tm = x & (m - 1)\n",
    "\t\t\tif not ok: continue\n",
    "\t\t\tm = y = (1 << n) - 1 - x\n",
    "\t\t\twhile m != 0:\n",
    "\t\t\t\tif calc(m) == s // 4: return True\n",
    "\t\t\t\tm = y & (m - 1)\n",
    "\t\treturn False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from gc import disable\n",
    "disable()\n",
    "class Solution:   \n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        edge, remain = divmod(sum(matchsticks), 4)\n",
    "        if remain: return False\n",
    "        matchsticks.sort(reverse=True)\n",
    "        @cache\n",
    "        def backtrace(u, st, cnt, status):\n",
    "            if u == edge:\n",
    "                if cnt + 1 == 4: return True\n",
    "                u = st = 0\n",
    "                cnt += 1\n",
    "            for i, x in enumerate(matchsticks[st:], st):\n",
    "                if ((status >> i) & 1) == 1: continue\n",
    "                if u + x > edge: continue\n",
    "                status |= 1 << i\n",
    "                if backtrace(u + x, i + 1, cnt, status): return True\n",
    "                status ^= 1 << i\n",
    "                if u == 0 or u + x == edge: break\n",
    "            return False\n",
    "        \n",
    "        return backtrace(0, 0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        n = len(matchsticks)\n",
    "        if sum(matchsticks) % 4 != 0:\n",
    "            return False\n",
    "\n",
    "        target = sum(matchsticks)//4\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(tmp, count, state):\n",
    "            if tmp == target and count == 4:\n",
    "                return True\n",
    "\n",
    "            if tmp > target:\n",
    "                return False\n",
    "\n",
    "            if count > 4:\n",
    "                return False\n",
    "\n",
    "            for i in range(n):\n",
    "                if (1 << i) & state == 0:\n",
    "\n",
    "                    if tmp == target:\n",
    "                        if dfs(matchsticks[i], count + 1, state | (1<<i)):\n",
    "                            return True\n",
    "\n",
    "                    else:\n",
    "                        if dfs(tmp + matchsticks[i], count, state | (1<<i)):\n",
    "                            return True\n",
    "\n",
    "\n",
    "                    if tmp == 0:\n",
    "                        return False\n",
    "\n",
    "            return False\n",
    "\n",
    "\n",
    "        matchsticks.sort(reverse = True)\n",
    "\n",
    "        return dfs(0, 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "\n",
    "        def f(i):\n",
    "            #if tuple(sorted(edges)) in d: return False\n",
    "            if i == n: return True\n",
    "            for k in range(4):\n",
    "                if k and edges[k-1] == edges[k]: continue\n",
    "                edges[k] += arr[i]\n",
    "                if edges[k] <= target and f(i + 1):\n",
    "                    return True\n",
    "                edges[k] -= arr[i]\n",
    "            d.add(tuple(sorted(edges)))\n",
    "            return False\n",
    "\n",
    "        arr = matchsticks\n",
    "        target, n =sum(arr), len(arr)\n",
    "        if target % 4: return False\n",
    "        target //= 4\n",
    "        arr.sort(reverse=True) \n",
    "        edges = [0] * 4 \n",
    "        d = set()\n",
    "\n",
    "        return f(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        sums = sum(nums)\n",
    "        if sums % 4:\n",
    "            return False\n",
    "        half1 = sums // 2\n",
    "        half2 = sums // 4\n",
    "        if max(nums) > half2:\n",
    "            return False\n",
    "        nums.sort(reverse = True)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, s0, s1, s2, s3):\n",
    "            if i == n:\n",
    "                if s0 == s3:\n",
    "                    return True\n",
    "                return False\n",
    "\n",
    "            s = [s0, s1, s2, s3]     \n",
    "            for j, x in enumerate(s):\n",
    "                if nums[i] + x <= half2:\n",
    "                    s_new = s[:]\n",
    "                    s_new[j] += nums[i]\n",
    "                    s_new.sort()\n",
    "                    if dfs(i+1, *s_new):\n",
    "                        return True\n",
    "                else:\n",
    "                    break        \n",
    "            return False\n",
    "\n",
    "        return dfs(0, 0, 0, 0, 0)                \n",
    "\n",
    "\n",
    "                    \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "                            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        n = len(matchsticks)\n",
    "        total = sum(matchsticks)\n",
    "        if total % 4 != 0:\n",
    "            return False\n",
    "        matchsticks.sort()\n",
    "        target = total // 4\n",
    "        if matchsticks[-1] > target:\n",
    "            return False\n",
    "        \n",
    "        @cache\n",
    "        def dfs(state, cur_sum) -> bool:\n",
    "            if state == (1 << n) - 1:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                if cur_sum + matchsticks[i] > target:\n",
    "                    break\n",
    "                if state & (1 << i) == 0:\n",
    "                    next_state = state | (1 << i)\n",
    "                    if dfs(next_state, (cur_sum + matchsticks[i]) % target):\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "\n",
    "        @cache\n",
    "        def dfs(state,c_val):\n",
    "\n",
    "            if state==(1<<n) - 1:\n",
    "                return True\n",
    "\n",
    "            for i in range(n):\n",
    "                if c_val + matchsticks[i] > targe:\n",
    "                    break\n",
    "                if state & (1<<i) == 0:\n",
    "                    next_state = state + (1<<i)\n",
    "                    if dfs(next_state,(c_val+matchsticks[i]) % targe):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        n=len(matchsticks)\n",
    "        targe=sum(matchsticks)//4\n",
    "        if sum(matchsticks)%4 != 0:\n",
    "            return False\n",
    "        matchsticks.sort()\n",
    "        if matchsticks[-1] > targe:\n",
    "            return False\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        # 回溯\n",
    "        # L = sum(matchsticks)\n",
    "        # if L % 4 != 0:\n",
    "        #     return False\n",
    "        \n",
    "        # l = L // 4\n",
    "        # if max(matchsticks) > l:\n",
    "        #     return False\n",
    "        # matchsticks.sort(reverse=True)\n",
    "\n",
    "        # edges = [0]*4\n",
    "        # # @cache\n",
    "        # def dfs(idx:int) -> bool:\n",
    "        #     if idx == len(matchsticks):\n",
    "        #         return True\n",
    "        #     for i in range(4):\n",
    "        #         edges[i] += matchsticks[idx]\n",
    "        #         if edges[i] <= l and dfs(idx+1):\n",
    "        #             return True\n",
    "        #         edges[i] -= matchsticks[idx] # 恢复现场\n",
    "        #     return False\n",
    "\n",
    "        # return dfs(0)\n",
    "\n",
    "\n",
    "\n",
    "        # 状态压缩 + 记忆搜索\n",
    "        @cache\n",
    "        def dfs(state, sum_):\n",
    "            if state == (1<<n)-1:\n",
    "                # 所有火柴一用，递归结束\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                if sum_ + matchsticks[i] > target:  \n",
    "                    # 火柴已升序， 当前i不可行，后续也不可行\n",
    "                    break\n",
    "                if state&(1<<i) == 0: # i未用\n",
    "                    next_state = state + (1<<i) # 使用i\n",
    "                    if dfs(next_state, (sum_ + matchsticks[i])%target):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        total = sum(matchsticks)\n",
    "        if total%4 != 0:\n",
    "            return False\n",
    "        target = total //4\n",
    "        matchsticks.sort()\n",
    "        if matchsticks[-1] > target:\n",
    "            return False\n",
    "        n = len(matchsticks)\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        n = len(matchsticks)\n",
    "        total = sum(matchsticks)\n",
    "        if total % 4 != 0:\n",
    "            return False\n",
    "        target = total // 4\n",
    "        matchsticks.sort()\n",
    "        if matchsticks[-1] > target:\n",
    "            return False\n",
    "        N = (1 << n) - 1\n",
    "        \n",
    "        @cache\n",
    "        def dfs(state, cur_sum):\n",
    "            if state == N:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                if cur_sum + matchsticks[i] > target:\n",
    "                    break\n",
    "                if state & (1 << i) == 0:\n",
    "                    new_state = state | (1 << i)\n",
    "                    if dfs(new_state, (cur_sum + matchsticks[i]) % target):\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        total = sum(matchsticks)\n",
    "        if total % 4: return False\n",
    "        t = total // 4\n",
    "        n = len(matchsticks)\n",
    "        matchsticks.sort()\n",
    "        if matchsticks[-1] > t: return False\n",
    "\n",
    "        @cache\n",
    "        def dfs(s, p):\n",
    "            if s == 0:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                if matchsticks[i] + p > t:\n",
    "                    break\n",
    "                if s >> i & 1 and dfs(s ^ (1 << i), (p + matchsticks[i]) % t):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs((1 << n) -  1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        total = sum(matchsticks)\n",
    "        if total % 4:\n",
    "            return False\n",
    "        piece = total // 4\n",
    "        matchsticks.sort()\n",
    "        if matchsticks[-1] > piece:\n",
    "            return False\n",
    "        @cache\n",
    "        def dsf(s, p):\n",
    "            if not s:\n",
    "                return True\n",
    "            for i in range(len(matchsticks)):\n",
    "                if p + matchsticks[i] > piece:\n",
    "                    break\n",
    "                if s & (1 << i) and dsf(s ^ (1 << i), (p + matchsticks[i]) % piece):\n",
    "                    return True\n",
    "            return False\n",
    "        return dsf((1 << len(matchsticks)) - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        #copy\n",
    "        total = sum(matchsticks)\n",
    "        if total%4!=0:\n",
    "            return False\n",
    "        line = total //4\n",
    "        if any(num > line for num in matchsticks):\n",
    "            return False\n",
    "        n = len(matchsticks)\n",
    "        final = (1<<n)-1\n",
    "        @cache\n",
    "        def dfs(state,cur):\n",
    "            if cur ==line:\n",
    "                cur =0\n",
    "                if state == final:\n",
    "                    return True\n",
    "            for i in range(n):\n",
    "                if not 1<<i&state and cur + matchsticks[i]<=line:\n",
    "                    if dfs(1<<i|state,cur+matchsticks[i]):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(0,0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        total = sum(matchsticks)\n",
    "        if total % 4 != 0:\n",
    "            return False\n",
    "        length = total // 4\n",
    "        edges = [0] * 4\n",
    "        if any(num > length for num in matchsticks):\n",
    "            return False\n",
    "        n = len(matchsticks)\n",
    "        matchsticks.sort(reverse=True)\n",
    "        # def dfs(i):\n",
    "        #     if i == n:\n",
    "        #         return True\n",
    "        #     for j in range(4):\n",
    "        #         edges[j] += matchsticks[i]\n",
    "        #         if edges[j] <= length and dfs(i+1):\n",
    "        #             return True\n",
    "        #         edges[j] -= matchsticks[i]\n",
    "        #     return False\n",
    "        # return dfs(0)\n",
    "\n",
    "        final = (1<<n) - 1\n",
    "        @cache\n",
    "        def dfs(state, cur):\n",
    "            if cur == length:\n",
    "                cur = 0\n",
    "                if state == final:\n",
    "                    return True\n",
    "            for i in range(n):\n",
    "                if not 1<<i & state and cur + matchsticks[i] <= length:\n",
    "                    if dfs(1<<i | state, cur+matchsticks[i]):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        tmp=sum(matchsticks)\n",
    "        target=tmp//4\n",
    "        if tmp%4!=0 or max(matchsticks)>target:\n",
    "            return False\n",
    "\n",
    "        n=len(matchsticks)\n",
    "        unactive=(1<<n)-1\n",
    "        #for i in range(n):\n",
    "        #    if matchsticks[i]==target:\n",
    "        #        unactive-=1<<i\n",
    "        sumnow=0\n",
    "\n",
    "        @cache\n",
    "        def dfs(unactive):\n",
    "            nonlocal sumnow\n",
    "            if unactive==0:\n",
    "                return True\n",
    "            for idx in range(n):\n",
    "                if (unactive>>idx & 1)==1 and matchsticks[idx]+sumnow<=target:\n",
    "                    sumnow=(0 if sumnow+matchsticks[idx]==target else sumnow+matchsticks[idx])\n",
    "                    unactive-=1<<idx\n",
    "                    if dfs(unactive):\n",
    "                        return True\n",
    "                    unactive+=1<<idx\n",
    "                    sumnow=(target-matchsticks[idx] if sumnow==0 else sumnow-matchsticks[idx]) \n",
    "\n",
    "            return False\n",
    "        return dfs(unactive)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        tmp=sum(matchsticks)\n",
    "        if tmp%4!=0:\n",
    "            return False\n",
    "\n",
    "        target=tmp//4\n",
    "        if max(matchsticks)>target:\n",
    "            return False\n",
    "        n=len(matchsticks)\n",
    "\n",
    "        unactive=(1<<n)-1\n",
    "        for i in range(n):\n",
    "            if matchsticks[i]==target:\n",
    "                unactive-=1<<i\n",
    "        print(format(unactive,'b'))\n",
    "\n",
    "        @cache\n",
    "        def dfs(unactive,sumnow):\n",
    "            if unactive==0:\n",
    "                return True\n",
    "            for idx in range(n):\n",
    "                if (unactive>>idx & 1)==1 and matchsticks[idx]+sumnow<=target:\n",
    "                    sumnow=(0 if sumnow+matchsticks[idx]==target else sumnow+matchsticks[idx])\n",
    "                    unactive-=1<<idx\n",
    "                    if dfs(unactive,sumnow):\n",
    "                        return True\n",
    "                    unactive+=1<<idx\n",
    "                    sumnow=(target-matchsticks[idx] if sumnow==0 else sumnow-matchsticks[idx]) \n",
    "\n",
    "            return False\n",
    "        return dfs(unactive,0)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        if sum(matchsticks)%4!=0:return False\n",
    "        length = sum(matchsticks)//4\n",
    "        if max(matchsticks)>length:return False\n",
    "        valid = []\n",
    "        for i in range(pow(2,len(matchsticks))):\n",
    "            if self.is_valid(matchsticks,i,length):\n",
    "                valid.append(i)\n",
    "        if valid==[]:return False\n",
    "        dic = {}\n",
    "        for i in valid:\n",
    "            for j in valid:\n",
    "                if i^j==i+j:\n",
    "                    if i in dic:dic[i].add(j)\n",
    "                    else:dic[i]=set([j])\n",
    "        for i in valid:\n",
    "            if i in dic:\n",
    "                for j in dic[i]:\n",
    "                    if j in dic:\n",
    "                        if dic[i]&dic[j]:\n",
    "                            return True\n",
    "        return False\n",
    "\n",
    "    def is_valid(self,matchsticks,i,length):\n",
    "        count = 0\n",
    "        for j in range(len(matchsticks)):\n",
    "            count+=matchsticks[j]*(i%2)\n",
    "            i>>=1\n",
    "        return count==length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        s = sum(matchsticks)\n",
    "        if s % 4 != 0:\n",
    "            return False\n",
    "        mod = s // 4\n",
    "        n = len(matchsticks)\n",
    "        mem_dict = dict()\n",
    "        def dfs(status):\n",
    "            nonlocal s\n",
    "            if status == 0:\n",
    "                return True\n",
    "            if status in mem_dict:\n",
    "                return mem_dict[status]\n",
    "            r = s % mod\n",
    "            if r == 0:\n",
    "                r = mod\n",
    "            for i, match_len in enumerate(matchsticks):\n",
    "                bit_index = 1 << i\n",
    "                if status & bit_index and match_len <= r:\n",
    "                    s -= match_len\n",
    "                    if dfs(status - bit_index):\n",
    "                        s += match_len\n",
    "                        mem_dict[status] = True\n",
    "                        return True\n",
    "                    s += match_len\n",
    "            mem_dict[status] = False\n",
    "            return False\n",
    "        return dfs((1<<n)-1)\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        if sum(matchsticks)%4!=0:\n",
    "            return False\n",
    "        dp = {}\n",
    "        side = sum(matchsticks) // 4\n",
    "        m = len(matchsticks)\n",
    "\n",
    "        def dfs(flg, side_num, tmp_sum):\n",
    "            if flg in dp:\n",
    "                return dp[flg]\n",
    "            if side_num == 3:\n",
    "                dp[flg] = True\n",
    "                return True\n",
    "            for i in range(m):\n",
    "                if (flg >> i) & 1 == 0:\n",
    "                    if (tmp_sum + matchsticks[i]) < side and dfs(flg + (1 << i), side_num, tmp_sum + matchsticks[i]):\n",
    "                        dp[flg] = True\n",
    "                        return True\n",
    "                    elif (tmp_sum + matchsticks[i]) == side and dfs(flg + (1 << i), side_num + 1, 0):\n",
    "                        dp[flg] = True\n",
    "                        return True\n",
    "            dp[flg] = False\n",
    "            return False\n",
    "\n",
    "        ans = dfs(0, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def makesquare(self, nums):\n",
    "        if not nums or sum(nums) % 4 != 0 or len(nums)<4:\n",
    "            return False\n",
    "        nums.sort(reverse=True)\n",
    "        L = len(nums)\n",
    "        perimeter = sum(nums)\n",
    "        possible_side = perimeter // 4\n",
    "        memo = set() #每个mask视为一个状态，如果某个状态已经遍历过得不到解，那直接返回False,1表示还没用过，0表示已经用过了\n",
    "        def recurse(mask):\n",
    "            total = 0\n",
    "            for i in range(L):\n",
    "                if not (mask & (1 << i)):\n",
    "                    total += nums[i]\n",
    "            if total % possible_side == 0 and total // possible_side == 3: #已经填满了三条边，第四条边肯定符合答案\n",
    "                return True\n",
    "            if mask in memo:\n",
    "                return False\n",
    "            rem = possible_side * (total//possible_side + 1) - total\n",
    "            for i in range(L):\n",
    "                if nums[i] <= rem and mask & (1 << i):\n",
    "                    if recurse(mask ^ (1 << i)):\n",
    "                        return True         \n",
    "            memo.add(mask)\n",
    "            return False\n",
    "        return recurse((1 << L) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        bucket = [0] * 4\n",
    "        nums = sorted(matchsticks, reverse=True)\n",
    "        if sum(nums) % 4 != 0:\n",
    "            return False\n",
    "        target = sum(nums) // 4\n",
    "        select = 0\n",
    "        st = set()\n",
    "        def divide(b_indx):\n",
    "            nonlocal select\n",
    "            if b_indx == 4:\n",
    "                return True\n",
    "            for i in range(0, len(nums)):\n",
    "                if select & (1 << i) != 0:\n",
    "                    continue\n",
    "                bucket[b_indx] += nums[i]\n",
    "                select += (1 << i)\n",
    "                if select in st:\n",
    "                    select -= (1 << i)\n",
    "                    bucket[b_indx] -= nums[i]\n",
    "                    continue\n",
    "                if bucket[b_indx] < target:\n",
    "                    if divide(b_indx):\n",
    "                        return True\n",
    "                    st.add(select)\n",
    "                if bucket[b_indx] == target:\n",
    "                    if divide(b_indx + 1):\n",
    "                        return True\n",
    "                    st.add(select)\n",
    "                select -= (1 << i)\n",
    "                bucket[b_indx] -= nums[i]\n",
    "            return False\n",
    "        return divide(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        tg = sum(matchsticks)\n",
    "        if tg % 4:\n",
    "            return False\n",
    "        tg = tg // 4\n",
    "        matchsticks.sort(reverse=True)\n",
    "        if matchsticks[0] > tg:\n",
    "            return False\n",
    "\n",
    "        @cache\n",
    "        def dfs(length, deep, mks):\n",
    "            if length < 0:\n",
    "                return False\n",
    "\n",
    "            if length == 0:\n",
    "                deep += 1\n",
    "                if deep == 4:\n",
    "                    return True\n",
    "                if dfs(tg, deep, mks):\n",
    "                    return True\n",
    "                return False\n",
    "\n",
    "            for idx, i in enumerate(mks):\n",
    "                if dfs(length - i, deep, mks[:idx] + mks[idx+1:]):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(tg, 0, tuple(matchsticks))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        @cache\n",
    "        def dfs(state, t):\n",
    "            \n",
    "            if state == (1 << len(matchsticks)) - 1:\n",
    "                return True\n",
    "            for i, v in enumerate(matchsticks):\n",
    "                if (state & (1 << i)):\n",
    "                    continue\n",
    "                if t + v > s:\n",
    "                    break\n",
    "                if dfs(state | (1 << i), (t + v) % s):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        s, mod = divmod(sum(matchsticks), 4)\n",
    "        matchsticks.sort()\n",
    "        if mod:\n",
    "            return False\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, nums: List[int]) -> bool:\n",
    "        self.length=len(nums)\n",
    "        if self.length<4:\n",
    "            return False\n",
    "        s=sum(nums)\n",
    "        if s%4!=0:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        self.target=s//4\n",
    "        if nums[-1]>self.target:\n",
    "            return False\n",
    "        return self._makesquare(tuple(nums),0,0)\n",
    "    @lru_cache(None)\n",
    "    def _makesquare(self,nums,cur,count):\n",
    "        if count==4:\n",
    "            return True\n",
    "        for i in range(len(nums)):\n",
    "            if cur+nums[i]==self.target:\n",
    "                if self._makesquare(nums[:i]+nums[i+1:],0,count+1):\n",
    "                    return True\n",
    "            elif cur+nums[i]<self.target:\n",
    "                if self._makesquare(nums[:i]+nums[i+1:],cur+nums[i],count):\n",
    "                    return True\n",
    "            else:\n",
    "                return False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        # def add_stick(i, sticks):\n",
    "        #     nonlocal side_length\n",
    "        #     if i == len(matchsticks):\n",
    "        #         return len(set(sticks)) == 1\n",
    "        #     for j in range(4):\n",
    "        #         sticks[j] += matchsticks[i]\n",
    "        #         if sticks[j] <= side_length and add_stick(i+1, sticks):\n",
    "        #             return True\n",
    "        #         sticks[j] -= matchsticks[i]\n",
    "        #     return False \n",
    "\n",
    "        # if (side_length := sum(matchsticks)) % 4:\n",
    "        #     return False \n",
    "        # side_length //= 4\n",
    "        # matchsticks.sort(reverse=True) # cannot pass w/o sort!!\n",
    "        # return add_stick(0, [0] * 4)\n",
    "\n",
    "        # --------------------------------------\n",
    "        @cache\n",
    "        def add_stick(state, cur_val):\n",
    "            nonlocal n, side_length\n",
    "            if state == 0:\n",
    "                return True \n",
    "            for i in range(n):\n",
    "                if state>>i & 1:\n",
    "                    if matchsticks[i] + cur_val <= side_length:\n",
    "                        if add_stick(state^(1<<i), (cur_val+matchsticks[i])%side_length):\n",
    "                            return True\n",
    "            return False\n",
    "        \n",
    "        n = len(matchsticks)\n",
    "        side_length, div_val = divmod(sum(matchsticks), 4)\n",
    "        if div_val:\n",
    "            return False\n",
    "        return add_stick((1<<n)-1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 等价于lc698,只不过本题固定k=4\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        acc = sum(matchsticks)\n",
    "        if acc % 4 : return False\n",
    "        target = acc // 4\n",
    "        @cache\n",
    "        def dfs(i,now,used):\n",
    "            if i == 4: return True\n",
    "            if now == target: return dfs(i + 1,0,used)\n",
    "            for j in range(len(matchsticks)):\n",
    "                if (used >> j) & 1 or now + matchsticks[j] > target: continue\n",
    "                if dfs(i,now + matchsticks[j],used | (1 << j)): return True\n",
    "            return False\n",
    "        return dfs(0,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 等价于lc698,只不过本题固定k=4\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        acc = sum(matchsticks)\n",
    "        n = (1 << len(matchsticks)) - 1\n",
    "        if acc % 4 : return False\n",
    "        target = acc // 4\n",
    "        cur = 0\n",
    "        # @cache\n",
    "        memo = {}\n",
    "        def dfs(cur, used):\n",
    "            if used == n: \n",
    "                return True\n",
    "            if (cur, used) in memo:\n",
    "                return memo[(cur, used)]\n",
    "            if cur == target: \n",
    "                return dfs(0, used)\n",
    "            \n",
    "            for j in range(len(matchsticks)):\n",
    "                if (used >> j) & 1 or cur + matchsticks[j] > target: \n",
    "                    continue\n",
    "                if dfs(cur + matchsticks[j], used | (1 << j)): \n",
    "                    return True\n",
    "            memo[(cur, used)] = False\n",
    "            return False\n",
    "        return dfs(0, 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
